package seqlist.LeetCode;
//83. 删除排序链表中的重复元素

/**
 * 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
 */

/**
 * 思路一:用双指针 prve 和 node。这是个排序的链表。如果当prve和node相等时，
 * prve所指向的节点肯定是第一次出现，而node指向的指针就是所谓的重复数了。
 * 让node一直向后走，当node不等于prve时，才后prve向后走一步。
 * 注释：node肯定是每次都要向后走的，node == null结束
 */
/*

public class Num_83_deleteDuplicates {

    public ListNode deleteDuplicates(ListNode head) {

        //特殊情况：当head为空，或者只有一个元素的时候，肯定没有重复元素存在
        if(head == null || head.next == null){
            return head;
        }

        ListNode prve = head;
        ListNode node = head.next;

        while(node != null){

            if(prve.val == node.val){
                //前后相等的时候，出现重复元素
                node = node.next;
                prve.next = node;//更新prve所指向的地址
            }else{
                //两个数不相等，依次向后移动
                prve = node;
                node = node.next;
            }
        }
        return head;

    }

}

 */

/**
 * 思路二：递归方法。他们只给我们头节点，所以我们给只处理头节点是否是重复数
 * 剩下的交给子方法去解决。 看返回节点的头节点。如果这是重复数，那么就已经被子方法
 * 删的只剩下一个了，再与原来的头节点相比较是否需要删除，如果返回的不是重复数就正常连接就可以了
 */
public class Num_83_deleteDuplicates {

    public ListNode deleteDuplicates(ListNode head) {

        //终止条件：当head为空，或者只有一个元素的时候，肯定没有重复元素存在
        if(head == null || head.next == null){
            return head;
        }else{
            //到这里说明至少存在两个节点，可能会出现重复元素
            head.next = deleteDuplicates(head.next);
            if(head.val == head.next.val){
                return head.next;//正在删除还得看这步
            }
            return head;
        }

    }

}
